package 中等.树;

import util.Node;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
 * <p>
 * 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
 */
public class N叉树的层序遍历_428 {

    public static void main(String[] args) {

        Node root = new Node(1);
        Node node3 = new Node(3);
        Node node2 = new Node(2);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        List<Node> list = new ArrayList<>();
        List<Node> list2 = new ArrayList<>();

        list.add(node3);
        list.add(node2);
        list.add(node4);

        list2.add(node5);
        list2.add(node6);
        root.children = list;
        node3.children = list2;

        System.out.println(levelOrder(root));

    }

    /**
     * 广度优先搜索
     * 每组子节点都由 null 值分隔，这句话根本不用管，树节点中的不会为null的节点，正常看做一个N叉树就行！！！
     *
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> lists = new ArrayList<>();
        Deque<Node> queue = new ArrayDeque<>();
        if (root != null) queue.addLast(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> curList = new ArrayList<>();  //一层一个list
            while (size-- > 0) {
                Node curNode = queue.pollFirst();
                curList.add(curNode.val);
                if (curNode.children != null) {
                    for (Node nextNode : curNode.children) {
                        queue.addLast(nextNode);
                    }
                }
            }
            lists.add(curList);
        }
        return lists;
    }

}
